\documentclass[E:/GsjzTle/main/main.tex]{subfiles}

\begin{document}

\begin{itemize}
\item
  \(n\) 个点 \(m\) 条边的无向连通图，边有边权。
\item
  求一个的生成树，使得其边权集合的 \(\text{mex}\) 尽可能小
\item
  \(1\le n \le 10^6,1\le m \le 2\times 10^6,0\le w \le 10^5\)（注意边权是从
  \(0\) 开始，要处理一下）
\end{itemize}

可撤销并查集+线段树分治\\
若一条边边权为 \(w\)，则给 \([1,w-1]\)、\([w+1,max]\) 添加上这条边。\\
若在叶子节点 \(size[find(1)]=n\) 则表示该图连通，直接输出
\textbf{叶子节点编号\(-1\)}（边权是从 \(0\) 开始的）即可

\begin{lstlisting}
typedef pair<int , int> pii;
const int N = 1e5 + 10 , M = 1e6 + 10;
int n , m;
int far[M] , size[M];
void init()
{
	rep(i , 1 , M - 10) far[i] = i , size[i] = 1;
}
int find(int x)
{
	if(x == far[x]) return x;
	return find(far[x]);
}
void Union(int x , int y , stack<pii>&st)
{
	int tx = find(x) , ty = find(y);
	if(tx != ty)
	{
		if(size[tx] > size[ty]) swap(tx , ty);
		st.push(make_pair(tx , ty));
		far[tx] = ty;
		size[ty] += size[tx];
	}
}
void Redo(stack<pii>&st)
{
	while(!st.empty()) 
	{
		pair<int , int>u = st.top();
		st.pop();
		far[u.fi] = u.fi;
		size[u.se] -= size[u.fi];
	}
}
struct Edge{
	int u , v , w;
	bool operator < (const Edge & b) const {
		return w < b.w;
	}
}edge[M << 1];
struct Tree{
	int l , r;
	vector<Edge>vec;
}tree[N << 2];
void build(int l , int r , int rt)
{
	tree[rt].l = l , tree[rt].r = r;
	if(l == r) return ;
	int mid = l + r >> 1;
	build(l , mid , rt << 1);
	build(mid + 1 , r , rt << 1 | 1);
}
void update_range(int L , int R , int rt , Edge e)
{
	int l = tree[rt].l , r = tree[rt].r;
	if(L <= l && r <= R)
	{
		tree[rt].vec.pb(e);
		return ;
	}
	int mid = l + r >> 1;
	if(L <= mid) update_range(L , R , rt << 1 , e);
	if(R  > mid) update_range(L , R , rt << 1 | 1 , e);
}
void query(int rt)
{
	int l = tree[rt].l , r = tree[rt].r;
	stack<pii>st;
	for(auto i : tree[rt].vec) Union(i.u , i.v , st);
	if(l == r)
	{
		if(size[find(1)] == n) 
		{
			cout << l - 1 << '\n';
			exit(0);
		}
	}
	else query(rt << 1) , query(rt << 1 | 1);
	Redo(st);
}
signed main()
{
	init();
	cin >> n >> m;
	int up = 1e5 + 1;
	build(1 , up , 1);
	rep(i , 1 , m)
	{
		int u , v , w;
		cin >> u >> v >> w;
		w ++ ;
		edge[i] = Edge{u , v , w + 1};	
		if(w != 1) update_range(1 , w - 1 , 1 , edge[i]);
		update_range(w + 1 , up , 1 , edge[i]); 
	}
	query(1);
	return 0;
}
\end{lstlisting}

\end{document}
